workers = []
tasks = []

def readData():
    with open("synthetic/1000_1000.txt",'r') as f:
        data = f.readlines()
        first = data[0].strip("\n").split(" ")
        workerNum = int(first[0])
        taskNum = int(first[1])
        for i in range(1,len(data)):
            node = data[i].strip("\n").split(" ")
            if node[1]=='w':
                node[0]=int(node[0])#到达时间
                node[2]=float(node[2])#纬度
                node[3]=float(node[3])#经度
                node[4]=float(node[4])#半径
                node[5]=int(node[5])#能力
                node[6]=int(node[6])+node[0]#停留的时间
                node[7]=float(node[7])#接受率
                if len(node) < 9:#最后一个用来记录等待多久匹配
                    node.append(0)
                else:
                    node[8] = 0
                workers.append(node)
            else:
                node[0]=int(node[0])#到达时间
                node[2]=float(node[2])#纬度
                node[3]=float(node[3])#经度
                node[4]=int(node[4])+node[0]#停留的时间
                node[5]=float(node[5])#支付的报酬
                if len(node) < 7:
                    node.append(0)
                else:
                    node[6] = 0
                tasks.append(node)
    return workerNum,taskNum

workerNum,taskNum = readData()
print(workerNum,taskNum)
import math,time,psutil,os
INF = 10e10

def length(worker:list,task:list)->float:#求两个点的长度
    distance = (worker[2]-task[2])**2+(worker[3]-task[2])**2
#     print(distance)
    distance = pow(distance,1/2)
    return distance
#     print(distance)

def length2(worker:list,task:list)->float:#求两个点的长度,不开方的
    distance = (worker[2]-task[2])**2+(worker[3]-task[3])**2
    return distance

def satisfyLoc(worker:list,task:list)->bool:#验证任务与工作者之间是否符合活动范围内
    if length2(worker,task) > worker[4]*worker[4]:
        return False
    return True

def satifyTime(worker:list,task:list)->bool:
    if (worker[0] < task[4] and task[0] < worker[6]) is False:
        return False
    return True

def satify(worker:list,task:list)->bool:
    if satifyTime(worker,task) and satisfyLoc(worker,task):
        return True
    return False
    

def calcCost(worker:list,task:list)->float:
    if satisfyLoc(worker,task) and satifyTime(worker,task):
        return worker[7]*task[5]
    else:
        return 0.0

def dcmp(a:float,b:float)->bool:
    return math.isclose(a,b,rel_tol=1e-6)
def dcmp(a:float)->bool:
    return abs(a)<1e-6

class KM:
    def __init__(self,workerlist,tasklist):#初始化相关参数
        self.workerlist = workerlist
        self.tasklist = tasklist
        self.wsize = len(workerlist)
        self.tsize = len(tasklist)
#         self.slack = INF
        self.slacks = []###
        self.weight = []#存放二分图中所有连接关系
        self.lx = []
        self.ly = []
        self.xy = []
        self.yx = []
        self.visitx = []
        self.visity = []
    
    def build(self,flag):#flag =true时候工作者数量小于任务数量
        if flag:#一般情况需要左边的节点少于右边节点，因为我选择右边节点开始遍历，如果右边节点多余左边节点会出现完全匹配时候无法退出dfs
            self.lx = [0.0 for i in range(self.wsize)]
            self.ly = [0.0 for i in range(self.tsize)]
            self.xy = [-1 for i in range(self.wsize)]
            self.yx = [-1 for i in range(self.tsize)]
            self.visitx = [False for i in range(self.wsize)]
            self.visity = [False for i in range(self.tsize)]
            for x in range(self.wsize):#初始化每一个工作者与任务连接
                temp = []
                for y in range(self.tsize):
                    u = calcCost(self.workerlist[x],self.tasklist[y])
                    temp.append(u)
                    self.lx[x] = max(u,self.lx[x])#找出与权重最大的工作者---任务对
                self.weight.append(temp)
                    
        else:#工作者数量大于任务数量
            self.lx = [0.0 for i in range(self.tsize)]
            self.ly = [0.0 for i in range(self.wsize)]
            self.xy = [-1 for i in range(self.tsize)]
            self.yx = [-1 for i in range(self.wsize)]
            self.visitx = [False for i in range(self.tsize)]
            self.visity = [False for i in range(self.wsize)]
            for x in range(self.tsize):
                temp = []
                for y in range(self.wsize):
                    u = calcCost(self.workerlist[y],self.tasklist[x])
                    temp.append(u)
                    self.lx[x] = max(u,self.lx[x])
                self.weight.append(temp)
    def success(self,flag):
        #计算效用
        utility = 0.0
        if flag:
            for w,t in enumerate(self.xy):
                if t!=-1:
                    u = self.weight[w][t]
                    if u > 0.0:
                        utility +=u
        else:
            for t,w in enumerate(self.xy):
                if w!=-1:
                    u = self.weight[t][w]
                    if u > 0.0:
                        utility +=u

        return utility
    #搜索路径
    def dfs(self,x:int)->bool:
        self.visitx[x] = True
        for y,flag in enumerate(self.visity):
            if flag:
                continue
            temp = self.lx[x] + self.ly[y] - self.weight[x][y]
#             temp = self.lx[x] + self.ly[y] - calcCost(self.workerlist[x],self.tasklist[y])
            if dcmp(temp):
                self.visity[y] = True
                if self.yx[y] == -1 or self.dfs(self.yx[y]):
                    self.xy[x] = y
                    self.yx[y] = x
                    return True
            else:
                self.slack = min(self.slack,temp)
                self.slacks[y] = min(self.slacks[y],temp)###
        return False 
    
    def match(self):
        ans = 0.0
        wtflag = False
        
        if self.wsize <= self.tsize:#工作者作为左边节点
            if self.wsize == 0 or self.tsize == 0:
                ans[1] = self.workerlist
                ans[2] = self.tasklist
                return ans
            wtflag = True
            self.build(wtflag)
            for x in range(self.wsize): 
                self.slacks = [INF for i in range(self.tsize)]###
                while True:
                    self.visitx = [False for i in range(self.wsize)]
                    self.visity = [False for i in range(self.tsize)]
                    self.slack = INF
                    #wsize<tsize
                    if self.dfs(x):
                        break

                    #更新访问过的节点, 因为self.wsize <= self.tsize，这里还可以优化加速
                    mm = INF###
                    for i,flag in enumerate(self.visity):###
                        if flag == False:###
                            mm = min(self.slacks[i],mm)###
                    for i,flag in enumerate(self.visitx):
                        if flag:
#                             self.lx[i] -= self.slack
                            self.lx[i] -= mm###
                    for i,flag in enumerate(self.visity):
                        if flag:
#                             self.ly[i] += self.slack
                            self.ly[i] += mm###
                        else:###
                            self.slacks[i] -= mm###
            ans = self.success(wtflag)#工作者左边
            return ans

        else:#任务作为左边节点
            if self.wsize == 0 or self.tsize == 0:
                ans[1] = self.workerlist
                ans[2] = self.tasklist
                return ans
            wtflag = False
            self.build(wtflag)
            for x in range(self.tsize):
                self.slacks = [INF for i in range(self.wsize)]###
                while True:
                    self.visitx = [False for i in range(self.tsize)]
                    self.visity = [False for i in range(self.wsize)]
                    self.slack = INF
                    if self.dfs(x):
                        break
                    #更新访问过的节点, 因为self.wsize > self.tsize，这里还可以优化加速
                    mm = INF###
                    for i,flag in enumerate(self.visity):###
                        if flag == False:###
                            mm = min(self.slacks[i],mm)###
                            
                    for i,flag in enumerate(self.visitx):
                        if flag:
                            self.lx[i] -= self.slack
                            self.lx[i] -= mm###
                    for i,flag in enumerate(self.visity):
                        if flag:
                            self.ly[i] += self.slack
#                             self.ly[i] += mm###
                        else:###
                            self.slacks[i] -= mm###
            ans = self.success(wtflag)#任务左边
            return ans
import resource
usage = resource.getrusage(resource.RUSAGE_SELF)
pid = os.getpid()
startMemory = psutil.Process(pid).memory_info().rss
startTime = time.perf_counter()
assignmment = KM(workers,tasks)
ans = assignmment.match()
endTIme = time.perf_counter()
endMemory = psutil.Process(pid).memory_info().rss
print(f"Memory usage: {usage.ru_maxrss / 1024:.2f}MB")

print(ans,(endTIme-startTime),(endMemory-startMemory))